package pers.qianyu.month_202011.date_20201130;

import java.util.*;

/**
 * 354. 俄罗斯套娃信封问题
 * https://leetcode-cn.com/problems/russian-doll-envelopes/
 *
 * @author mizzle rain
 * @date 2020-11-30 16:34
 */
public class MaxEnvelopes {
    public int maxEnvelopes(int[][] envelopes) {
        if (envelopes == null || envelopes.length == 0) {
            return 0;
        }
        // 按照长度升序，如果长度相同，就按照宽度降序
        Arrays.sort(envelopes, (o1, o2) -> o1[0] - o2[0] != 0 ? o1[0] - o2[0] : o2[1] - o1[1]);
        int[] dp = new int[envelopes.length];
        Arrays.fill(dp, 1);
        for (int i = 1; i < dp.length; i++) {
            for (int k = 0; k < i; k++) {
                if (envelopes[i][1] > envelopes[k][1]) {
                    dp[i] = Math.max(dp[i], dp[k] + 1);
                }
            }
        }
        int res = dp[0];
        for (int i = 1; i < dp.length; i++) {
            if (res < dp[i]) {
                res = dp[i];
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int[][] arr = {
                {5, 4}, {6, 4}, {6, 7}, {2, 3}
        };
        int result = new MaxEnvelopes().maxEnvelopes(arr);
        System.out.println("result = " + result);
    }
}
